package com.gitee.feizns.explore.data_structure.tree.bs.mid;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 894. 所有可能的满二叉树
 * @author feizns
 * @since 2020/3/14
 */
public class AllPossibleFBT {

    public static void main(String[] args) {
        final List<TreeNode> nodes = allPossibleFBT(5);
        System.out.println(nodes);
    }

    static Map<Integer, List<TreeNode>> map = new HashMap<>();

    public static List<TreeNode> allPossibleFBT(int N) {
        List<TreeNode> nodes = map.get(N);
        if ( nodes != null )
            return nodes;
        if ( N == 1 )
            map.put(1, Arrays.asList(new TreeNode(0)));
        else if ( N % 2 == 1 ) {
            allPossibleFBT(N - 2);
            List<TreeNode> tmp = new ArrayList<>();
            for (int i = 1; i < N; i+=2) {
                List<TreeNode> left = map.get(i);
                List<TreeNode> right = map.get(N - i -1);
                for (TreeNode l : left) {
                    for (TreeNode r : right) {
                        TreeNode t = new TreeNode(0);
                        t.left = l;
                        t.right = r;
                        tmp.add(t);
                    }
                }
            }
            map.put(N, tmp);
            return tmp;
        }
        return Collections.emptyList();
    }

}
